package 算法.NiuKe.JZ;

import 算法.NiuKe.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author:谢君臣
 * @Date:2021/3/2020:11
 * @version:1.0
 * @function: 题目描述
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 * 示例1
 * 输入
 * {8,8,#,9,#,2,#,5},{8,9,#,2}
 * 返回值
 * true
 */
public class JZ17 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        root = new TreeNode(8);
        root.left = new TreeNode(8);
//        root.right = new TreeNode(3);
        root.left.left = new TreeNode(9);
        root.left.left.left = new TreeNode(2);
        root.left.left.left.left = new TreeNode(5);
        TreeNode treeNode = new TreeNode(8);
        treeNode.left = new TreeNode(9);
        treeNode.left.left = new TreeNode(2);

        System.out.println(HasSubtree(root, treeNode));

    }

    public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
        boolean re = false;
        if (root1 == null || root2 == null)
            return false;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root1);
        while (!queue.isEmpty()) {
            TreeNode p = queue.poll();
            if (p.left != null) queue.add(p.left);
            if (p.right != null) queue.add(p.right);
            if (check(p, root2)){
                re = true;
                break;
            }
        }
        return re;
    }

    private static boolean check(TreeNode p, TreeNode root2) {
        if (p == null || root2 == null) {
            if (p == root2)
                return true;
            else if (root2==null)
                return true;
            else
                return false;
        } else {
            if (p.val == root2.val) {
                boolean l = check(p.left, root2.left);
                boolean r = check(p.right, root2.right);
                return l == r && l;
            } else
                return false;
        }
    }
}
